Partiel de mathématiques discrètes, semestre 1, juin 2009. Durée : 3 heures.

Couchot, J.-F.

Les supports de TDs et de TP sont autorisés ; téléphones et calculatrices sont interdits. Q. 1. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive si

∀(x, y) ∈ E^{2}, (x, y) ∈ G et (y, x) ∈ G ⟹ x = y. L’assertion proposée est vraie ou fausse ?

Q. 2. Un ordre sur E est dit partiel si, lorsque l’on choisit deux éléments quelconques x et y dans E, alors x est en relation avec y, ou y est en relation avec x. L’assertion proposée est vraie ou fausse ?

Q. 3. R = {(x, y) ∈ ℝ^{2}, xy = 1} est une relation fonctionnelle. L’assertion proposée est vraie ou fausse ?

Q. 4. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive si ∀x ∈ E, xRx. L’assertion proposée est vraie ou fausse ?

Q. 5. xRy ⟺ « x et y ont le même reste dans une division par 2 » est une relation d’équivalence sur les entiers strictement positifs. L’assertion proposée est vraie ou fausse ?

Q. 6. | (divisibilité) est une relation d’ordre totale dans ℕ. L’assertion proposée est vraie ou fausse ? Q. 7. (ℝ, ⩽) est un ensemble ordonné. L’assertion proposée est vraie ou fausse ? Q. 8. Les relations d’equivalence sont les relations réflexive, symétrique et transitive. L’assertion pro-

posée est vraie ou fausse ?

Q. 9. | (relation de divisibilité) est une relation d’ordre partiel dans ℕ. L’assertion proposée est vraie ou fausse ? Q. 10. Soit (E, R) un ensemble ordonné, et A une partie de E. On appelle minorant de A tout élément

x de E tel que, quel que soit a ∈ A, aRx. L’assertion proposée est vraie ou fausse ?

Q. 11. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite antisymétrique quand tout élément est en relation avec lui-même. L’assertion proposée est vraie ou fausse ?

Q. 12. Soit R une relation binaire. Il est possible d’avoir xRy sans avoir yRx. L’assertion proposée est vraie ou fausse ?

Q. 13. Si f : E ⟶ F est bijective, alors tout élément de F possède exactement un antécédant dans E. L’assertion proposée est vraie ou fausse ?

Q. 14. | est une relation d’ordre dans ℤ. L’assertion proposée est vraie ou fausse ? Q. 15. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite symétrique si

∀(x, y, z) ∈ E^{3}, (x, y) ∈ G et (y, z) ∈ G ⟹ (x, z) ∈ G. L’assertion proposée est vraie ou fausse ?

Q. 16. « xRy si et seulement si sin(x) = sin(y) » est une relation d’ordre sur l’ensemble des réels. L’assertion proposée est vraie ou fausse ?

Q. 17. Soit (E, R) un ensemble ordonné, et A une partie de E. On appelle majorant de A tout élément x de E tel que, quel que soit a ∈ A, aRx. L’assertion proposée est vraie ou fausse ?

Q. 18. Les relations d’equivalence sont les relations réflexive, antisymétrique et transitive. L’assertion proposée est vraie ou fausse ?

Q. 19. √ : ℝ^{+} ⟶ ℝ est surjective. L’assertion proposée est vraie ou fausse ? Q. 20. Un ordre sur E est dit partiel si, lorsque l’on choisit deux éléments quelconques x et y dans E,

alors x est en relation avec y, ou y est en relation avec x. L’assertion proposée est vraie ou fausse ?

Q. 21. Une application de E dans F est telle que ∀x ∈ E, il existe un unique élément y ∈ F en relation avec x. L’assertion proposée est vraie ou fausse ?

Q. 22. Un ordre est dit total sur E si tous les éléments de E sont comparables entre eux. L’assertion proposée est vraie ou fausse ?

Q. 23. Une application est une relation binaire particulière. L’assertion proposée est vraie ou fausse ?

Q. 24. Une partie A de E est dite majorée s’il existe une borne supérieure pour A. L’assertion proposée est vraie ou fausse ?

Q. 25. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite réflexive si

∀(x, y) ∈ E^{2}, xRy ⟹ yRx

L’assertion proposée est vraie ou fausse ?

Q. 26. Soit (E, R) un ensemble ordonné. Il peut exister des parties de E qui sont non majorées. L’assertion proposée est vraie ou fausse ?

Q. 27. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite antisymétrique si

∀(x, y) ∈ E^{2}, xRy et yRx ⟹ x = y

L’assertion proposée est vraie ou fausse ?

Q. 28. « xRy si et seulement si sin(x) = sin(y) » est une relation d’equivalence sur l’ensemble des réels. L’assertion proposée est vraie ou fausse ?

Q. 29. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite antisymétrique si, lorsque x est en relation avec y, alors y ne peut pas être en relation avec x (sauf si x = y). L’assertion proposée est vraie ou fausse ?

Q. 30. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite symétrique si ∀(x, y) ∈ E^{2}, xRy et yRx ⟹ x = y. L’assertion proposée est vraie ou fausse ?

Q. 31. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite réflexive si ∀x ∈ E, xRx. L’assertion proposée est vraie ou fausse ?

Q. 32. L’égalité de deux entiers est une relation d’équivalence. L’assertion proposée est vraie ou fausse ? Q. 33. Si f : E ⟶ F est bijective, alors tout élément de E possède exactement une image dans F.

L’assertion proposée est vraie ou fausse ?

Q. 34. ⩽ est une relation d’ordre total dans ℝ. L’assertion proposée est vraie ou fausse ? Q. 35. Les relations d’ordre sont les relations réflexive, antisymétrique et transitive. L’assertion proposée

est vraie ou fausse ?

Q. 36. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive si ∀(x, y) ∈ E^{2}, (x, y) ∈ G et (y, x) ∈ G ⟹ x = y. L’assertion proposée est vraie ou fausse ?

Q. 37. sin : ℝ ⟶ [−1, 1] est injective. L’assertion proposée est vraie ou fausse ? Q. 38. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite antisymétrique si,

lorsque x est en relation avec y, alors y est en relation avec x. L’assertion proposée est vraie ou fausse ?

Q. 39. Une partie A de E est dite majorée s’il existe un minorant pour A. L’assertion proposée est vraie ou fausse ?

Q. 40. Etant données les fonctions f : A → B, g : B → C et h : C → D définies par le diagramme suivant

abc  1 2 3  x yz w  4 5 6 A  B  C  D f  g  h

h ∘ g est-elle surjective ? Q. 41. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite antisymétrique si

∀(x, y) ∈ E^{2}, xRy ⟹ yRx. L’assertion proposée est vraie ou fausse ?

Q. 42. (P(E), ⊂) est un ensemble ordonné. L’assertion proposée est vraie ou fausse ? Q. 43. (ℤ, |) est un ensemble ordonné. L’assertion proposée est vraie ou fausse ? Q. 44. Soit R la relation dans A = {1, 2, 3, 4} définie par R = {(1, 3), (1, 4), (3, 2), (3, 3), (3, 4), }.

A-t-on R ∘ R = {(1, 3) × (1, 3), (1, 3) × (1, 4), (1, 3) × (3, 2), …, (3, 3) × (3, 4), (3, 4) × (3, 4)}?

Q. 45. Etant donnée la relation R dans C = {1, 2, 3, 4, 5} définie par les points figurant dans le diagramme cartésien :

012345 _{0 1 2 3 4 5}

Le domaine de R est-il {1, 2, 4, 5}? Q. 46. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive lorsque,

si x est en relation avec y, et si y l’est avec z, alors x est en relation avec z. L’assertion proposée est vraie ou fausse ?

Q. 47. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite symétrique si

∀(x, y) ∈ E^{2}, xRy ⟹ yRx

L’assertion proposée est vraie ou fausse ?

Q. 48. Si f : E ⟶ F est bijective, alors tout élément de F possède exactement un antécédant dans E. L’assertion proposée est vraie ou fausse ?

Q. 49. Soit (E, R) un ensemble ordonné, et A une partie de E. On appelle minimum de A tout élément x de E tel que, quel que soit a ∈ A, aRx. L’assertion proposée est vraie ou fausse ?

Q. 50. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite antisymétrique si

∀(x, y, z) ∈ E^{3}, (x, y) ∈ G et (y, z) ∈ G ⟹ (x, z) ∈ G

L’assertion proposée est vraie ou fausse ?

Q. 51. Une partie A peut être non majorée, mais admettre quand même un élément maximum. L’assertion proposée est vraie ou fausse ?

Q. 52. Un ordre est dit partiel sur E si tous les éléments de E sont comparables entre eux. L’assertion proposée est vraie ou fausse ?

Q. 53. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive si, lorsque x est en relation avec y, alors y est en relation avec x. L’assertion proposée est vraie ou fausse ?

Q. 54. Une application injective est une application telle que tout élément de l’ensemble de départ possède au plus une image. L’assertion proposée est vraie ou fausse ?

Q. 55. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive si, lorsque x est en relation avec y, alors y ne peut pas être en relation avec x (sauf si x = y). L’assertion proposée est vraie ou fausse ?

Q. 56. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite symétrique si, lorsque x est en relation avec y, alors y est en relation avec x. L’assertion proposée est vraie ou fausse ?

Q. 57. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite réflexive si, lorsque x est en relation avec y, alors y ne peut pas être en relation avec x (sauf si x = y). L’assertion proposée est vraie ou fausse ?

Q. 58. Etant données les fonctions f : A → B, : g : B → C et h : C → D définies par le diagramme suivant

abc  1 2 3  x yz w  4 5 6 A  B  C  D f  g  h

On ne peut pas déduire du schéma des propriétés de h ∘ h. Q. 59. Dans une algèbre de Boole munie des opérateurs classiques +, .et , on considère l’expression

E = \overline{a}(a + b)(a + c)(a + d)(a + e). La version la plus réduite de E est \overline{a}bcde. L’assertion proposée est vraie ou fausse ?

Q. 60. Etant donnée la relation R dans C = {1, 2, 3, 4, 5} définie par les points figurant dans le diagramme cartésien :

012345 _{0 1 2 3 4 5}

Le domaine de R est-il {1, 2, 3, 4, 5}? Q. 61. sin : ℝ ⟶ [−1, 1] est surjective. L’assertion proposée est vraie ou fausse ? Q. 62. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive quand

tout élément est en relation avec lui-même. L’assertion proposée est vraie ou fausse ?

Q. 63. √ : ℝ^{+} ⟶ ℝ est surjective. L’assertion proposée est vraie ou fausse ? Q. 64. | (relation de divisibilité) est une relation d’ordre partiel dans ℕ. L’assertion proposée est vraie

ou fausse ?

Q. 65. L’égalité de deux entiers est une relation d’équivalence. L’assertion proposée est vraie ou fausse ? Q. 66. Les relations d’equivalence sont les relations réflexive, symétrique et transitive. L’assertion pro-

posée est vraie ou fausse ?

Q. 67. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite réflexive quand tout élément est en relation avec lui-même. L’assertion proposée est vraie ou fausse ?

Q. 68. Soit W = {1, 2, 3, …, 7, 8} et un sous-ensemble V = {4, 5, 6} de W. W est ordonné comme ci-dessous où X → Y si X est inférieur à Y :

1  2 3 4  5 6  7 8

{1,2,3} est l’ensemble des majorants de V . Vrai ou Faux ? Q. 69. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive si,

lorsque x est en relation avec y, alors y est en relation avec x. L’assertion proposée est vraie ou fausse ?

Q. 70. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite symétrique si ∀x ∈ E, xRx. L’assertion proposée est vraie ou fausse ?

Q. 71. ⩽ est une relation d’ordre partiel dans ℝ. L’assertion proposée est vraie ou fausse ? Q. 72. Soit t_{1} et t_{2} deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +,

.et . Si t_{1} + t_{2} = 1 alors t_{1} = 1 et t_{2} a une valeur quelconque, et vice versa. L’assertion proposée est vraie ou fausse ?

Q. 73. sin : ℝ ⟶ [−1, 1] est surjective. L’assertion proposée est vraie ou fausse ? Q. 74. On appelle élément maximum de A un élément de A qui est majorant de A. L’assertion proposée

est vraie ou fausse ?

Q. 75. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite symétrique si, lorsque x est en relation avec y, alors y ne peut pas être en relation avec x (sauf si x = y). L’assertion proposée est vraie ou fausse ?

Q. 76. Une application bijective est surjective. L’assertion proposée est vraie ou fausse ? Q. 77. Soit R une relation binaire définie sur un ensemble E, de graphe G. R est dite transitive si,

lorsque x est en relation avec y, alors y ne peut pas être en relation avec x (sauf si x = y). L’assertion proposée est vraie ou fausse ?

Q. 78. Soit une relation d’ordre sur E, de graphe G. Cette relation d’ordre est dite totale si ∀x, y ∈ E, (x, y) ∈ G ou (y, x) ∈ G. L’assertion proposée est vraie ou fausse ?

Q. 79. Soit W = {1, 2, 3, …, 7, 8} et un sous-ensemble V = {4, 5, 6} de W. W est ordonné comme ci-dessous où X → Y si X est inférieur à Y :

1  2 3 4  5 6  7 8

Les éléments 6 et 8 sont les minorants de V . Vrai ou Faux ? Q. 80. Soit W = {1, 2, 3, …, 7, 8} et un sous-ensemble V = {4, 5, 6} de W. W est ordonné comme

ci-dessous où X → Y si X est inférieur à Y :

1  2 3 4  5 6  7 8

L’élément 8 est le seul minorant de V . Vrai ou Faux ?